package main

import "fmt"

// 堆排序：属于选择类排序算法——不稳定排序算法

// 优先级队列
// 优先队列是一种能完成以下任务的队列：插入一个数值，取出最小或最大的数值（获取数值，并且删除）。
// 优先队列可以用二叉树来实现，我们称这种结构为二叉堆。
// 最小堆和最大堆是二叉堆的一种，是一棵完全二叉树（一种平衡树）。
// 最小堆的性质：
// 	父节点的值都小于左右儿子节点。
//	这是一个递归的性质。
//
// 最大堆的性质：
//	父节点的值都大于左右儿子节点。
//	这是一个递归的性质。
//
//最大堆和最小堆实现方式一样，只不过根节点一个是最大的，一个是最小的。

// Heap 最大堆实现
// 最大堆要求节点元素都不小于其左右孩子
type Heap struct {
	// 堆的大小
	Size int
	// 使用内部的数组来模拟树
	// 一个节点下标为i, 那么其父亲节点的下标为：(i - 1) / 2
	// 一个节点下标为i, 那么其左儿子的下标为 2i + 1, 右儿子下标为 2i + 2
	Array []int
}

// NewHeap 初始化一个堆
func NewHeap(array []int) *Heap {
	h := new(Heap)
	h.Array = array
	return h
}

// Push 最大堆插入元素
// 上浮操作
func (h *Heap) Push(x int) {
	// 堆没有元素时，使元素成为顶点后退出
	if h.Size == 0 {
		h.Array[0] = x
		h.Size++
		return
	}
	// i是要插入节点的下标
	i := h.Size
	// 如果下标存在,将小的值x一直上浮
	for i > 0 {
		// parent为该元素父亲节点的下标
		parent := (i - 1) / 2

		// 如果插入的值小于父亲节点，那么可以退出循环
		if x <= h.Array[parent] {
			break
		}

		// 否则将父亲节点于该节点互换，然后向上翻转，将最大的元素一直往上推
		h.Array[i] = h.Array[parent]
		i = parent
	}
	// 将x放在不会再翻转的位置
	h.Array[i] = x
	// 堆数量 + 1
	h.Size++
}


// Pop 最大堆移除根节点元素，也就是最大的元素
// 下沉操作
func (h *Heap) Pop() int {
	// 没有元素，返回 - 1
	if h.Size == 0 {
		return -1
	}
	// 取出根节点
	ret := h.Array[0]
	h.Size--

	x := h.Array[h.Size]   // 拿出最后一个元素的值
	h.Array[h.Size] = ret  // 将移除的元素放在最后一个元素的位置上

	// 对根节点进行向下翻转，小的x一直下沉，维持最大堆的特征
	i := 0
	for {
		// 左右子节点下标
		l := 2 * i + 1
		r := 2 * i + 2

		// 左儿子下标超出，表示没有左子树，那么右子树也没有，直接返回
		if l >= h.Size {
			break
		}
		// 有右子树，拿到两个子结点中较大节点的下标
		if r < h.Size && h.Array[r] > h.Array[l] {
			l = r
		}

		// 父亲节点的值都大于或者等于两个儿子较大的那个，不需要向下继续翻转，返回即可
		if x >= h.Array[l] {
			break
		}
		// 将较大的子节点与父节点交换，维持最大堆特征
		h.Array[i] = h.Array[l]

		// for循环继续进行下沉操作
		i = l
	}

	// 将最后一个元素的值 x 放在不会再翻转的位置
	h.Array[i] = x
	return ret
}

// HeapSort 堆排序实现——最大堆
// 普通版本实现
func HeapSort(array []int) {
	// 初始化堆结构体
	h := NewHeap(array)
	// 构建最大堆
	for _, v := range array {
		h.Push(v)
	}

	// 将利用最大堆Pop函数，进行堆排序操作，
	for range array {
		h.Pop()
	}

}

// HeapSort2 自底向上堆排序实现——优化算法
func HeapSort2(array []int) {
	// 堆的元素数量
	count := len(array)
	// 最底层的叶子节点下标，该节点位置不定，但是该叶子节点右边的节点都是叶子节点
	start := count / 2 + 1
	// 最后的元素下标
	end := count - 1
	
	// 从最底层开始，逐一对节点进行下沉操作
	for start >= 0 {
		sift(array, start, count)
		start--		// 表示左偏移一个节点，如果该层没有节点，表示到了上一层的最右边
	}

	// 下沉结束，开始排序
	// 元素数量大于2的最大堆才可以移除
	for end > 0 {
		// 将堆顶元素与堆尾元素互换，表示移除最大堆元素
		array[end], array[0] = array[0], array[end]
		// 对堆顶元素进行下沉操作
		sift(array, 0, end)
		// 一直移除堆顶元素
		end--
	}
}

// 下沉操作，需要下沉的元素是array[start], 参数count用来判断是否到达堆底，使得下沉结束
func sift(array []int, start int, count int) {
	// 父节点
	root := start

	// 左儿子
	child := root * 2 + 1

	// 如果有下一代
	for child < count {
		// 右节点比左节点大，翻转取最大值
		if count - child > 1 && array[child] < array[child + 1] {
			child++
		}
		// 父节点比子节点小，互换
		if array[root] < array[child] {
			array[root], array[child] = array[child], array[root]
			// 继续下沉
			root = child
			child = root * 2 + 1
		} else {
			return
		}
	}
}

func main() {

	list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	HeapSort2(list)
	// 打印排序后的序列
	fmt.Println(list)

}

































